/*
 * @lc app=leetcode.cn id=827 lang=java
 *
 * [827] 最大人工岛
 */



import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.HashSet;

// @lc code=start
class Solution {
    public int largestIsland(int[][] grid) {
        int value = 2;
        // 岛屿编号---面积
        Map<Integer, Integer> map = new HashMap<>();

        for(int r = 0; r < grid.length; r++) {
            for(int c = 0; c < grid[0].length; c++) {
                if(grid[r][c] == 1) {
                    // 求出面积
                    int a = area(grid, r, c, value);

                    map.put(value, a);

                    value++;
                }
            }
        }

        int res = 0;
        for(int r = 0; r < grid.length; r++) {
            for(int c = 0; c < grid[0].length; c++) {
                int tmp = thisArea(grid, r, c, map);
                res = Math.max(res, tmp);
            }
        }
        return res;

    }

    // 将 (r, c)填海后，最大的岛屿面积
    private int thisArea(int[][] grid, int r, int c, Map<Integer, Integer> map) {
        // 如果是陆地---返回面积
        if(grid[r][c] != 0) {
            return map.get(grid[r][c]);
        }

        int res = 0;
        Set<Integer> adjs = new HashSet<>();
        if(inArea(grid, r-1, c) && grid[r-1][c] > 0) {
            adjs.add(grid[r-1][c]);
        }
        if(inArea(grid, r+1, c) && grid[r+1][c] > 0) {
            adjs.add(grid[r+1][c]);
        }
        if(inArea(grid, r, c-1) && grid[r][c-1] > 0) {
            adjs.add(grid[r][c-1]);
        }
        if(inArea(grid, r, c+1) && grid[r][c+1] > 0) {
            adjs.add(grid[r][c+1]);
        }

        for(int adj : adjs) {
            res += map.get(adj);
        }

        return res + 1;
    }

    // value: 岛屿编号 ---将岛屿部分格子填写为value
    private int area(int[][] grid, int r, int c, int value) {
        if(!inArea(grid, r, c)) {
            return 0;
        }

        if(grid[r][c] != 1) {
            return 0;
        }

        grid[r][c] = value;

        return 1 + area(grid, r - 1, c, value) + area(grid, r + 1, c, value) + area(grid, r, c - 1, value) + area(grid, r, c + 1, value);
    }

    private boolean inArea(int[][] grid, int r, int c) {
        return r >= 0 && r < grid.length && c >= 0 && c < grid[0].length;
    }
}
// @lc code=end

